{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 对Word2Vec的一点理解\n",
    "\n",
    "这一周仔细研究了一下自然语言处理方面（NLP）的一个大问题，Word2Vec。并且针对这个问题手动用代码实现了一下。所谓Word2Vec就是将自然语言中的词汇转化成向量形式。在传统的转化方案中大多是利用one-hot编码，也就是说若一个语料库中拥有三万个词汇，那么每一个词转化成的向量就会拥有三万维，整个语料库变成了一个巨大的稀疏矩阵，这对内存和计算力来说都是不小的挑战。后来随着神经网络的兴起，Word2Vec摆脱了以往傻大黑粗的转化方式，开始利用神经网络进行编码，当然这是另一个分枝了。今天笔者要讲的是Google提出的一种Word2Vec的方式，这种方式不但可以将词汇用有限的维数表达（通常不超过150维），而且还能够保留词与词之间的语义联系。话不多说，下面开始详细介绍。\n",
    "\n",
    "## 介绍\n",
    "\n",
    "由Google提出的这种Word2Vec模型是有着非常深厚的数学基础，在介绍这种方法之前首先我们应该先了解这个模型的两种应用。第一种是CBOW(Continuous Bag of Words)，另一种是Skip-Gram。这两种Word2Vec模型都是语义预测模型，数学推导非常相近，用于解决两类截然不同的问题。CBOW用于解决通过上下文预测中心词的问题，也就是说我们给出一句话的上下文，要求该模型能够预测出中心词是什么。Skip-Gram模型则恰恰相反，它用于预测上下文，就是说我们给出一个中心词，要求模型能够给出与该中心词相关的上下文。在本文中笔者以Skip-Gram模型为基础介绍算法的一些细节和实现。\n",
    "\n",
    "## 数学基础\n",
    "\n",
    "Skip-Gram模型中已经给出了模型的目标：就是要根据中心词预测出上下文词汇。该模型是依据概率论中的观点，建立一个似然函数来实现模型的目的。该模型的本质还是去解一个最优化问题的解，其优化问题的表达就是上文提到的那个似然函数。在Skip-Gram模型中待优化的目标函数可以写成如下形式：\n",
    "\n",
    "$$G=\\prod_{\\omega \\in C}^{ }\\prod_{u \\in Context(\\omega )}^{ }g(u)$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上式中w就是模型中传入的中心词，u是w的上下文中的词。该优化函数所要表达的意思就是。在整个语料库C的范围内，给出任意一个词w，预测出其上下文u的概率要最大化。接下来我们再给出g(u)的形式：\n",
    "\n",
    "$$g(u)=\\prod_{z\\in \\{u\\}\\cup NEG(u)}^{ }p(z|\\omega )$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上式中NEG(u)为负样本集合，何为负样本？考虑Skip-Gram模型的这样一个输入(w, context(x))，若该输入的标签不为context(w)，则我们就说这个样本为一个负样本。其中，p(z|w)的概率可以表达为如下形式：\n",
    "\n",
    "$$p(z|\\omega )=\\left\\{\n",
    "\\begin{aligned}\n",
    "&\\sigma (v(\\omega )^{T}\\theta ^{z}), L^{u}(z)=1\\\\\n",
    "&1-\\sigma (v(\\omega )^{T}\\theta ^{z}), L^{u}(z)=0\n",
    "\\end{aligned}\n",
    "\\right.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从上面的表达式可以看出该概率表达式将预测问题转化成了一个二分类问题，每个分类的结果用概率表示。分类正确的概率表达为sigmod函数下中心词的向量乘以一个参数，该参数是未知的。而分类错误的概率为一减分类正确的概率。上面概率用一个式子可以表达为：\n",
    "\n",
    "$$p(z|\\omega )=[\\sigma (v(\\omega )^{T}\\theta ^{z})]^{L^{u}(z)}[1-\\sigma (v(\\omega )^{T}\\theta ^{z})]^{1-L^{u}(z)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们可以对G取似然函数，也就是取log对数得到如下表达：\n",
    "\n",
    "$$\\begin{align*}\n",
    "L=logG&=log\\prod_{\\omega \\in C}^{ }\\prod_{u \\in Context(\\omega )}^{ }\\prod_{z\\in \\{u\\}\\cup NEG(u)}^{ }p(z|\\omega )\\\\\n",
    "&=\\sum_{\\omega \\in C}^{ }\\sum_{u \\in Context(\\omega )}^{ }\\sum_{z\\in \\{u\\}\\cup NEG(u)}^{ }log\\ p(z|\\omega )\\\\\n",
    "&=\\sum_{\\omega \\in C}^{ }\\sum_{u \\in Context(\\omega )}^{ }\\sum_{z\\in \\{u\\}\\cup NEG(u)}^{ }log\\ \\{[\\sigma (v(\\omega )^{T}\\theta ^{z})]^{L^{u}(z)}[1-\\sigma (v(\\omega )^{T}\\theta ^{z})]^{1-L^{u}(z)}\\}\\\\\n",
    "&=\\sum_{\\omega \\in C}^{ }\\sum_{u \\in Context(\\omega )}^{ }\\sum_{z\\in \\{u\\}\\cup NEG(u)}^{ }\\{L^{u}(z)log\\ [\\sigma (v(\\omega )^{T}\\theta ^{z})]+(1-L^{u}(z))log\\ [1-\\sigma (v(\\omega )^{T}\\theta ^{z})]\\}\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上式就是Skip-Gram模型的似然函数或者说优化函数了，我们接下来只需要求该似然函数关于v(w)和theta的偏导就能求解该问题了。然而在实际中我们并不是使用这个似然函数作为优化目标的，因为从该似然函数的形式中也可以看出，该似然函数针对每个词w的上下文context(w)都要求进行|context(w)|次负采样，这样的计算量太大，因此，我们重新定义一个似然函数，形式如下：\n",
    "\n",
    "$$\\begin{align*}\\\n",
    "L=logG&=log\\prod_{\\omega \\in C}^{ }\\prod_{\\tilde{\\omega} \\in Context(\\omega )}^{ }\\prod_{u\\in \\{\\omega\\}\\cup NEG(\\omega)}^{ }p(u|\\tilde{\\omega} )\\\\\n",
    "&=\\sum_{\\omega \\in C}^{ }\\sum_{\\tilde{\\omega} \\in Context(\\omega )}^{ }\\sum_{u\\in \\{\\omega\\}\\cup NEG(\\omega)}^{ }log\\ p(u|\\tilde{\\omega} )\\\\\n",
    "&=\\sum_{\\omega \\in C}^{ }\\sum_{\\tilde{\\omega} \\in Context(\\omega )}^{ }\\sum_{u\\in \\{\\omega\\}\\cup NEG(\\omega)}^{ }log\\ \\{[\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]^{L^{\\omega}(u)}[1-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]^{1-L^{\\omega}(u)}\\}\\\\\n",
    "&=\\sum_{\\omega \\in C}^{ }\\sum_{\\tilde{\\omega} \\in Context(\\omega )}^{ }\\sum_{u\\in \\{\\omega\\}\\cup NEG(\\omega)}^{ }\\{L^{\\omega}(u)log\\ [\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]+(1-L^{\\omega}(u))log\\ [1-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]\\}\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如上面的似然函数所示，现在针对一个context(w)只用一次负样本抽样就可以了。为了方便，我们将花括号内部的式子用一个标记代替：\n",
    "\n",
    "$$L(\\omega ,\\tilde{\\omega},u)=L^{\\omega}(u)log\\ [\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]+(1-L^{\\omega}(u))log\\ [1-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]$$\n",
    "\n",
    "则似然函数现在写作：\n",
    "\n",
    "$$L=\\sum_{\\omega \\in C}^{ }\\sum_{\\tilde{\\omega} \\in Context(\\omega )}^{ }\\sum_{u\\in \\{\\omega\\}\\cup NEG(\\omega)}^{ }L(\\omega ,\\tilde{\\omega},u)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们求解这个最优化问题。首先，我们求解该似然函数关于theta的导数，在求解之前首先要补充一个关于sigmod函数求导的公式，因为似然函数中的概率是以sigmod函数为基础计算的：\n",
    "\n",
    "$$[log\\ sigmod(x)]^{'}=[1-sigmod(x)]x^{'}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有了以上的基础知识我们就能够求似然函数关于theta的偏导函数了：\n",
    "\n",
    "$$\\begin{align*}\\\n",
    "\\frac{\\partial L(\\omega ,\\tilde{\\omega},u)}{\\partial \\theta ^{u}}&= \\frac{\\partial\\{L^{\\omega}(u)log\\ [\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]+(1-L^{\\omega}(u))log\\ [1-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]\\}}{\\partial \\theta^{u}}\\\\\n",
    "&=L^{\\omega}(u)(1-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u}))v(\\tilde{\\omega})-[1-L^{\\omega}(u)]\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})v(\\tilde{\\omega} )\\\\\n",
    "&=[L^{\\omega}(u)-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]v(\\tilde{\\omega} )\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接着就能够构建关于theta的梯度更新公式，由于我们这里是最大化L，因此采用梯度上升公式：\n",
    "\n",
    "$$\\theta^{u}:=\\theta^{u}+\\eta [L^{\\omega}(u)-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]v(\\tilde{\\omega} )$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "然后我们求似然函数关于v(w)的偏导数，由于在式中v(w)和theta是以相乘关系在一起的，因此求关于v(w)的偏导结果可以参照关于theta的偏导结果直接给出：\n",
    "\n",
    "$$\\begin{align*}\\\n",
    "\\frac{\\partial L(\\omega ,\\tilde{\\omega},u)}{\\partial v(\\tilde{\\omega} )}&= \\frac{\\partial\\{L^{\\omega}(u)log\\ [\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]+(1-L^{\\omega}(u))log\\ [1-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]\\}}{\\partial v(\\tilde{\\omega} )}\\\\\n",
    "&=[L^{\\omega}(u)-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]\\theta^{u}\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "词汇的向量编码更新公式为：\n",
    "\n",
    "$$v(\\tilde{\\omega} ):=v(\\tilde{\\omega} )+\\eta \\sum_{u\\in \\{\\omega\\}\\cup NEG(\\omega)}^{ }[L^{\\omega}(u)-\\sigma (v(\\tilde{\\omega} )^{T}\\theta ^{u})]\\theta^{u}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "至于这里为什么要写成累加的形式是因为每个w向量的表达形式都是由{w} U NEG(w)来决定的，因此在计算梯度公式的时候也一定要将这些分量的贡献值都加上去。现在，我们已经有了关于theta和v(w)的梯度更新公式，只用按照似然函数的累加关系来迭代优化就可以了。需要说明的是theta和v(w)可以用正态分布或随机数来初始化。最后笔者还想再提一下负采样算法，也就是似然函数最后一个累加符号的NEG(w)该如何产生。\n",
    "\n",
    "## 负采样算法\n",
    "\n",
    "这种算法首先需要使用者传入一个值，这个值指定了每一次负采样产生的负样本数量。对于CBOW模型，它的样本是这样一种形式：(context(x), x)，我们负采样的时候针对一个样本context(x)只用产生一个不同于x的标签值就可以了。而对于Skip-Gram模型，它的情况与CBOW模型恰恰相反，针对一个x，我们必须产生出一个不同于context(x)的上下文来。下面就介绍一下负采样算法的中心思想。\n",
    "\n",
    "假设现在有一个语料库C，我们通过词频统计计算出语料库中出现频率最高的前N个词汇。首先定义一个词汇的“长度”：\n",
    "\n",
    "$$len(\\omega )=\\frac{counter(\\omega)}{\\sum{counter(\\omega_{i})}}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "公式中的counter函数返回一个词在语料库中出现的频度。需要说明的是：在Google发布的Word2Vec中，词汇长度计算公式中分子分母上的每一个counter函数返回值均有一个0.75的乘幂。得到了N个词汇的“长度”之后，我们可以将这些长度随机地放置在一条长度为1的线段上，由于词汇“长度”的计算中采取的是类似于softmax的形式，因此这N个词汇的“长度”相加一定等于1。然后我们再设置一条长度为1的线段与前面的对应，在这条线段上等长划分出M个小线段（M>N），这样可以保证上面线段中每个区间在下面线段中均至少有一个M的划分对应。\n",
    "\n",
    "在负抽样时，我们首先传入负抽样的样本数记为c，程序在[1~m-1]的区间上产生c个随机数，然后再以这c个随机数为索引找到对应的m划分，每个m划分所对应的词汇长度线段所对应的词就是负抽样的结果。若我们对w词汇进行负抽样，不幸采样结果中也出现了w，那么标准的做法是删除这个采样结果再做一次。\n",
    "\n",
    "## 实现\n",
    "\n",
    "具体的实践部分详见github上的开源代码，下面只介绍一下实现的效果。实践部分笔者对一篇一千七百余万字的语料库做了分析，统计出出现频度前5000的词汇，并且用tensorflow的相关技术对Word2Vec做了实现，最后编码得到的5000个词汇向量如下所示：\n",
    "\n",
    "```\n",
    "[[ 0.00973416  0.01551841  0.01932655 ... -0.03791888 -0.05606225\n",
    "  -0.06215049]\n",
    " [-0.00267094  0.01791083  0.07254971 ... -0.02780523  0.09160008\n",
    "   0.09563514]\n",
    " [ 0.0083055   0.02367309 -0.12816067 ...  0.08717421 -0.17020826\n",
    "   0.01977647]\n",
    " ...\n",
    " [-0.05508857 -0.06620894  0.06096853 ...  0.02253385  0.02945674\n",
    "  -0.00181306]\n",
    " [ 0.13115096 -0.02681032 -0.1124193  ...  0.08576214 -0.02940259\n",
    "   0.05799532]\n",
    " [-0.01801354  0.10596514  0.1338353  ...  0.09485397  0.06949527\n",
    "   0.08904167]]\n",
    "```\n",
    "\n",
    "在出现频度排前100位的词汇进行随机抽样，随机抽取出8个词汇，分析其语义相近的词汇，结果如下：\n",
    "\n",
    "```\n",
    "Nearst to three : four - <0.734>, five - <0.729>, two - <0.720>, eight - <0.702>, zero - <0.698>, six - <0.689>, seven - <0.666>, one - <0.657>,\n",
    "Nearst to see : power - <0.414>, price - <0.409>, featuring - <0.381>, statue - <0.377>, constitutional - <0.376>, partly - <0.375>, convinced - <0.374>, fought - <0.373>,\n",
    "Nearst to not : converted - <0.438>, mathbf - <0.431>, also - <0.425>, breaking - <0.400>, really - <0.391>, to - <0.387>, purely - <0.387>, prevent - <0.379>,\n",
    "Nearst to are : were - <0.624>, is - <0.542>, attempting - <0.409>, all - <0.406>, jane - <0.406>, mathbf - <0.406>, be - <0.404>, monarchy - <0.403>,\n",
    "Nearst to which : that - <0.532>, welsh - <0.430>, found - <0.422>, this - <0.417>, creation - <0.409>, two - <0.403>, one - <0.401>, member - <0.400>,\n",
    "Nearst to these : similarities - <0.441>, remaining - <0.416>, engineering - <0.405>, drew - <0.404>, fusion - <0.378>, organism - <0.374>, vehicles - <0.369>, many - <0.366>,\n",
    "Nearst to as : mathbf - <0.483>, known - <0.433>, cdot - <0.432>, fear - <0.422>, fairly - <0.412>, aristotle - <0.408>, setting - <0.404>, mathematics - <0.404>,\n",
    "Nearst to two : one - <0.737>, three - <0.720>, zero - <0.719>, four - <0.705>, five - <0.688>, nine - <0.652>, eight - <0.647>, seven - <0.638>,\n",
    "Nearst to were : are - <0.624>, was - <0.502>, been - <0.448>, jane - <0.433>, jimmy - <0.413>, frequently - <0.402>, movements - <0.395>, have - <0.386>,\n",
    "Nearst to years : decades - <0.469>, rough - <0.438>, publication - <0.425>, latter - <0.423>, wallace - <0.384>, equal - <0.380>, invention - <0.380>, balance - <0.377>,\n",
    "Nearst to war : movie - <0.424>, ask - <0.406>, liquid - <0.395>, bass - <0.394>, edinburgh - <0.392>, drugs - <0.387>, pointed - <0.375>, funeral - <0.364>,\n",
    "Nearst to on : in - <0.450>, threatened - <0.416>, tone - <0.414>, relativity - <0.404>, february - <0.403>, seasons - <0.400>, excellent - <0.399>, by - <0.395>,\n",
    "Nearst to history : shakespeare - <0.449>, corn - <0.412>, workers - <0.398>, super - <0.394>, eventually - <0.388>, boat - <0.381>, tendency - <0.376>, experience - <0.372>,\n",
    "Nearst to its : the - <0.572>, their - <0.472>, his - <0.433>, fashion - <0.417>, jean - <0.382>, instruments - <0.379>, expected - <0.378>, goods - <0.374>,\n",
    "Nearst to over : daniel - <0.409>, received - <0.404>, solid - <0.401>, traffic - <0.400>, worked - <0.400>, requirements - <0.397>, feet - <0.392>, four - <0.390>,\n",
    "Nearst to had : has - <0.517>, namely - <0.427>, tests - <0.415>, have - <0.409>, prison - <0.393>, formally - <0.393>, broken - <0.386>, was - <0.384>,\n",
    "```\n",
    "\n",
    "结果中`<>`内部的数字是相似程度。观察结果的第一条：\n",
    "\n",
    "```\n",
    "Nearst to three : four - <0.734>, five - <0.729>, two - <0.720>, eight - <0.702>, zero - <0.698>, six - <0.689>, seven - <0.666>, one - <0.657>\n",
    "```\n",
    "\n",
    "可以看出，和“three”语义相近的词汇均是英文中的数字词汇，且相似度都在60%以上说明这个模型的效果还是比较不错的。\n",
    "\n",
    "2018年4月28日"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
